package TenBasicAlgorithm;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

//马踏棋盘（骑士周游问题）(递归回溯)+贪心
public class DiGuiHorsePedalChessboardDemo {
    private static int X;//行
    private static int Y;//列
    private static boolean visited[];
    private static boolean finished;

    public static void main(String[] args) {
        X=8;Y=8;
        int row=41;
        int column=1;
        int[][]chess=new int[X][Y];
        visited=new boolean[X*Y];
        long start=System.currentTimeMillis();
        HorsePedalChessboard(chess,row-1,column-1,1);
        long end=System.currentTimeMillis();
        System.out.println(end-start);//输出耗时
        for (int[]r:chess) {
            System.out.println(Arrays.toString(r));//输出棋盘的走法
        }
    }

    /**
     * 根据当前位置计算马可以走的位置（日字走法的落脚点）
     * @param curPoint
     * @return
     */
    public static ArrayList<Point> next(Point curPoint){//获取下一步所走的节点位置(因为通过贪心进行排序所以在此的策略便不是很重要)
        ArrayList<Point> ps = new ArrayList<>();
        Point p1=new Point();
        if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y+1)<Y){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+2)<X&&(p1.y=curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+2)<X&&(p1.y=curPoint.y+1)<Y){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y+2)<Y){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+1)<X&&(p1.y=curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+1)<X&&(p1.y=curPoint.y+2)<Y){
            ps.add(new Point(p1));
        }


        return ps;

    }

    /**
     *
     *
     * @param chess 棋盘
     * @param row 马的当前位置行
     * @param column 马的当前位置列
     * @param step 步数（一步一格）
     */
    public static void HorsePedalChessboard(int[][]chess,int row,int column,int step){
        chess[row][column]=step;
        visited[row*X+column]=true;
        ArrayList<Point> ps=next(new Point(column,row));
        sort(ps);
        while (!ps.isEmpty()){
            Point p=ps.remove(0);
            if(!visited[p.y*X+p.x]){
                HorsePedalChessboard(chess,p.y,p.x,step+1);
            }
        }
        if(step<X*Y&&!finished){
            chess[row][column]=0;
            visited[row*X+column]=false;//回溯
        }else {
            finished=true;
        }
    }
    public static void sort(ArrayList<Point> ps){//排序判断的过程
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {//根据当前节点的下一步的可走方案的大小来排序
                int count1=next(o1).size();
                int count2=next(o2).size();
                if(count1<count2){
                    return -1;
                }else if(count1==count2){
                    return 0;

                }else {
                    return 1;
                }
            }
        });
    }
}
